今天的題單：

• Implement Queue using Stacks

• First Bad Version

232. Implement Queue using Stacks

限制只使用兩個 stack 實作 queue，要支援 push、pop、peek、empty 操作

思路：假設有兩個 stack A, B

• push(): 直接 push 進 A

• pop(): 把 A 裡的 element 全部 pop 到 stack B → stack_B.pop()→把 stack B 裡的東西再全部 pop 倒回 A

• peek(): 把 A 裡的 element 全部 pop 到 stack B → stack_B.top() → 把 stack B 裡的東西再全部 pop 倒回 stack A

• empty(): 看 A 是不是空的

pop() 和 peek() 可以進一步優化：只有在 stack B 是空的時候才把 stack A 裡的 element 倒進去，讓 stack B 裡有東西的時候只要看最上面那個 element 就好。empty() 要改成檢查兩個 stack 是不是都是空的。

class MyQueue {
public:
    MyQueue() {
        
    }
    
    void push(int x) {
        this->A.push(x);
    }
    
    int pop() {
        int q_top;
        if (this->B.empty()) {
            while (!this->A.empty()) {
                this->B.push(this->A.top());
                this->A.pop();
            }
        }
        q_top = this->B.top();
        this->B.pop();
        return q_top;
    }
    
    int peek() {
        if (this->B.empty()) {
            while (!this->A.empty()) {
                this->B.push(this->A.top());
                this->A.pop();
            }
        }
        return this->B.top();
    }
    
    bool empty() {
        return this->A.empty() && this->B.empty();
    }

private:
    stack<int> A;
    stack<int> B;
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

這題 follow up 問有沒有 amortized O(1) time complexity 的實作，平均一個操作是 O(1)

以我的作法用 amortized analysis 分析總複雜度的話
push() 和 empty()：每次操作都是 O(1)，所以可以直接得出 amortized O(1)
pop() 和 peek()：有兩種情況

• 當 stack B 是空的時候，會需要把 stack_A 裡的元素搬到 stack_B，移動量是 O(n)

• 當 stack B 不是空的時候，只要移動 stack_B 頂端的元素，移動量是 O(1)

最差的情況是 n 次操作都是 pop()，但在這 n 次 pop 中只會出現一次 O(n) 的操作，其他都是 O(1)，因此總複雜度是 O(n)，平攤下來 pop()複雜度是是 O(n) / n = O(1)

278. First Bad Version

找第一個發生錯誤的版本。

思路 1：linear scan 過去找到第一個 bad version，時間複雜度是 O(n)。

思路 2：用 binary search 可以減少搜尋次數，時間複雜度是 O(logn)。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        // binary search
        return binary_search(n);
    }

    int binary_search(int n) {
        int left = 1;
        int right = n;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid) == false) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;

    }
};